home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / lib / mozilla-firefox / include / xpcom / nsDeque.h < prev    next >
C/C++ Source or Header  |  2006-05-08  |  11KB  |  406 lines
  1. /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
  2. /* ***** BEGIN LICENSE BLOCK *****
  3.  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
  4.  *
  5.  * The contents of this file are subject to the Mozilla Public License Version
  6.  * 1.1 (the "License"); you may not use this file except in compliance with
  7.  * the License. You may obtain a copy of the License at
  8.  * http://www.mozilla.org/MPL/
  9.  *
  10.  * Software distributed under the License is distributed on an "AS IS" basis,
  11.  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12.  * for the specific language governing rights and limitations under the
  13.  * License.
  14.  *
  15.  * The Original Code is mozilla.org code.
  16.  *
  17.  * The Initial Developer of the Original Code is
  18.  * Netscape Communications Corporation.
  19.  * Portions created by the Initial Developer are Copyright (C) 1998
  20.  * the Initial Developer. All Rights Reserved.
  21.  *
  22.  * Contributor(s):
  23.  *
  24.  * Alternatively, the contents of this file may be used under the terms of
  25.  * either of the GNU General Public License Version 2 or later (the "GPL"),
  26.  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  27.  * in which case the provisions of the GPL or the LGPL are applicable instead
  28.  * of those above. If you wish to allow use of your version of this file only
  29.  * under the terms of either the GPL or the LGPL, and not to allow others to
  30.  * use your version of this file under the terms of the MPL, indicate your
  31.  * decision by deleting the provisions above and replace them with the notice
  32.  * and other provisions required by the GPL or the LGPL. If you do not delete
  33.  * the provisions above, a recipient may use your version of this file under
  34.  * the terms of any one of the MPL, the GPL or the LGPL.
  35.  *
  36.  * ***** END LICENSE BLOCK ***** */
  37.  
  38. /**
  39.  * MODULE NOTES:
  40.  *
  41.  * The Deque is a very small, very efficient container object
  42.  * than can hold elements of type void*, offering the following features:
  43.  *    Its interface supports pushing and popping of elements.
  44.  *    It can iterate (via an interator class) its elements.
  45.  *    When full, it can efficiently resize dynamically.
  46.  *
  47.  *
  48.  * NOTE: The only bit of trickery here is that this deque is
  49.  * built upon a ring-buffer. Like all ring buffers, the first
  50.  * element may not be at index[0]. The mOrigin member determines
  51.  * where the first child is. This point is quietly hidden from
  52.  * customers of this class.
  53.  *
  54.  */
  55.  
  56. #ifndef _NSDEQUE
  57. #define _NSDEQUE
  58.  
  59. #include "nscore.h"
  60.  
  61. /**
  62.  * The nsDequeFunctor class is used when you want to create
  63.  * callbacks between the deque and your generic code.
  64.  * Use these objects in a call to ForEach();
  65.  *
  66.  */
  67.  
  68. class nsDequeFunctor{
  69. public:
  70.   virtual void* operator()(void* anObject)=0;
  71. };
  72.  
  73. /******************************************************
  74.  * Here comes the nsDeque class itself...
  75.  ******************************************************/
  76.  
  77. /**
  78.  * The deque (double-ended queue) class is a common container type,
  79.  * whose behavior mimics a line in your favorite checkout stand.
  80.  * Classic CS describes the common behavior of a queue as FIFO.
  81.  * A deque allows insertion and removal at both ends of
  82.  * the container.
  83.  *
  84.  * The deque stores pointers to items.
  85.  */
  86.  
  87. class nsDequeIterator;
  88.  
  89. class NS_COM nsDeque {
  90.   friend class nsDequeIterator;
  91.   public:
  92.    nsDeque(nsDequeFunctor* aDeallocator);
  93.   ~nsDeque();
  94.  
  95.   /**
  96.    * Returns the number of elements currently stored in
  97.    * this deque.
  98.    *
  99.    * @return  number of elements currently in the deque
  100.    */
  101.   inline PRInt32 GetSize() const {return mSize;}
  102.  
  103.   /**
  104.    * Appends new member at the end of the deque.
  105.    *
  106.    * @param   item to store in deque
  107.    * @return  *this
  108.    */
  109.   nsDeque& Push(void* aItem);
  110.  
  111.   /**
  112.    * Inserts new member at the front of the deque.
  113.    *
  114.    * @param   item to store in deque
  115.    * @return  *this
  116.    */
  117.   nsDeque& PushFront(void* aItem);
  118.  
  119.   /**
  120.    * Remove and return the last item in the container.
  121.    *
  122.    * @return  the item that was the last item in container
  123.    */
  124.   void* Pop();
  125.  
  126.   /**
  127.    * Remove and return the first item in the container.
  128.    *
  129.    * @return  the item that was first item in container
  130.    */
  131.   void* PopFront();
  132.  
  133.   /**
  134.    * Retrieve the bottom item without removing it.
  135.    *
  136.    * @return  the first item in container
  137.    */
  138.  
  139.   void* Peek();
  140.   /**
  141.    * Return topmost item without removing it.
  142.    *
  143.    * @return  the first item in container
  144.    */
  145.   void* PeekFront();
  146.  
  147.   /**
  148.    * Retrieve the i'th member from the deque without removing it.
  149.    *
  150.    * @param   index of desired item
  151.    * @return  i'th element in list
  152.    */
  153.   void* ObjectAt(int aIndex) const;
  154.  
  155.   /**
  156.    * Remove all items from container without destroying them.
  157.    *
  158.    * @return  *this
  159.    */
  160.   nsDeque& Empty();
  161.  
  162.   /**
  163.    * Remove and delete all items from container.
  164.    * Deletes are handled by the deallocator nsDequeFunctor
  165.    * which is specified at deque construction.
  166.    *
  167.    * @return  *this
  168.    */
  169.   nsDeque& Erase();
  170.  
  171.   /**
  172.    * Creates a new iterator, pointing to the first
  173.    * item in the deque.
  174.    *
  175.    * @return  new dequeIterator
  176.    */
  177.   nsDequeIterator Begin() const;
  178.  
  179.   /**
  180.    * Creates a new iterator, pointing to the last
  181.    * item in the deque.
  182.    *
  183.    * @return  new dequeIterator
  184.    */
  185.   nsDequeIterator End() const;
  186.  
  187.   void* Last() const;
  188.   /**
  189.    * Call this method when you want to iterate all the
  190.    * members of the container, passing a functor along
  191.    * to call your code.
  192.    *
  193.    * @param   aFunctor object to call for each member
  194.    * @return  *this
  195.    */
  196.   void ForEach(nsDequeFunctor& aFunctor) const;
  197.  
  198.   /**
  199.    * Call this method when you want to iterate all the
  200.    * members of the container, calling the functor you 
  201.    * passed with each member. This process will interrupt
  202.    * if your function returns non 0 to this method.
  203.    *
  204.    * @param   aFunctor object to call for each member
  205.    * @return  first nonzero result of aFunctor or 0.
  206.    */
  207.   const void* FirstThat(nsDequeFunctor& aFunctor) const;
  208.  
  209.   void SetDeallocator(nsDequeFunctor* aDeallocator);
  210.  
  211. protected:
  212.   PRInt32         mSize;
  213.   PRInt32         mCapacity;
  214.   PRInt32         mOrigin;
  215.   nsDequeFunctor* mDeallocator;
  216.   void*           mBuffer[8];
  217.   void**          mData;
  218.  
  219. private:
  220.  
  221.   /**
  222.    * Simple default constructor (PRIVATE)
  223.    */
  224.   nsDeque();
  225.  
  226.   /**
  227.    * Copy constructor (PRIVATE)
  228.    *
  229.    * @param another deque
  230.    */
  231.   nsDeque(const nsDeque& other);
  232.  
  233.   /**
  234.    * Deque assignment operator (PRIVATE)
  235.    *
  236.    * @param   another deque
  237.    * @return  *this
  238.    */
  239.   nsDeque& operator=(const nsDeque& anOther);
  240.  
  241.   PRInt32 GrowCapacity();
  242. };
  243.  
  244. /******************************************************
  245.  * Here comes the nsDequeIterator class...
  246.  ******************************************************/
  247.  
  248. class NS_COM nsDequeIterator {
  249. public:
  250.   /**
  251.    * DequeIterator is an object that knows how to iterate
  252.    * (forward and backward) through a Deque. Normally,
  253.    * you don't need to do this, but there are some special
  254.    * cases where it is pretty handy.
  255.    *
  256.    * One warning: the iterator is not bound to an item,
  257.    * it is bound to an index, so if you insert or remove
  258.    * from the beginning while using an iterator
  259.    * (which is not recommended) then the iterator will
  260.    * point to a different item.  @see GetCurrent()
  261.    *
  262.    * Here you go.
  263.    *
  264.    * @param   aQueue is the deque object to be iterated
  265.    * @param   aIndex is the starting position for your iteration
  266.    */
  267.   nsDequeIterator(const nsDeque& aQueue, int aIndex=0);
  268.  
  269.   /**
  270.    * Create a copy of a DequeIterator
  271.    *
  272.    * @param   aCopy is another iterator to copy from
  273.    */
  274.   nsDequeIterator(const nsDequeIterator& aCopy);
  275.  
  276.   /**
  277.    * Moves iterator to first element in the deque
  278.    * @return  *this
  279.    */
  280.   nsDequeIterator& First();
  281.  
  282.   /**
  283.    * Standard assignment operator for dequeiterator
  284.    * @param   aCopy is another iterator to copy from
  285.    * @return  *this
  286.    */
  287.   nsDequeIterator& operator=(const nsDequeIterator& aCopy);
  288.  
  289.   /**
  290.    * preform ! operation against two iterators to test for equivalence
  291.    * (or lack thereof)!
  292.    *
  293.    * @param   aIter is the object to be compared to
  294.    * @return  TRUE if NOT equal.
  295.    */
  296.   PRBool operator!=(nsDequeIterator& aIter);
  297.  
  298.   /**
  299.    * Compare two iterators for increasing order.
  300.    *
  301.    * @param   aIter is the other iterator to be compared to
  302.    * @return  TRUE if this object points to an element before
  303.    *          the element pointed to by aIter.
  304.    *          FALSE if this and aIter are not iterating over
  305.    *          the same deque.
  306.    */
  307.   PRBool operator<(nsDequeIterator& aIter);
  308.  
  309.   /**
  310.    * Compare two iterators for equivalence.
  311.    *
  312.    * @param   aIter is the other iterator to be compared to
  313.    * @return  TRUE if EQUAL
  314.    */
  315.   PRBool operator==(nsDequeIterator& aIter);
  316.  
  317.   /**
  318.    * Compare two iterators for non strict decreasing order.
  319.    *
  320.    * @param   aIter is the other iterator to be compared to
  321.    * @return  TRUE if this object points to the same element, or
  322.    *          an element after the element pointed to by aIter.
  323.    *          FALSE if this and aIter are not iterating over
  324.    *          the same deque.
  325.    */
  326.   PRBool operator>=(nsDequeIterator& aIter);
  327.  
  328.   /**
  329.    * Pre-increment operator
  330.    * Iterator will advance one index towards the end.
  331.    *
  332.    * @return  object_at(++index)
  333.    */
  334.   void* operator++();
  335.  
  336.   /**
  337.    * Post-increment operator
  338.    * Iterator will advance one index towards the end.
  339.    *
  340.    * @param   param is ignored
  341.    * @return  object_at(mIndex++)
  342.    */
  343.   void* operator++(int);
  344.  
  345.   /**
  346.    * Pre-decrement operator
  347.    * Iterator will advance one index towards the beginning.
  348.    *
  349.    * @return  object_at(--index)
  350.    */
  351.   void* operator--();
  352.  
  353.   /**
  354.    * Post-decrement operator
  355.    * Iterator will advance one index towards the beginning.
  356.    *
  357.    * @param   param is ignored
  358.    * @return  object_at(index--)
  359.    */
  360.   void* operator--(int);
  361.  
  362.   /**
  363.    * Retrieve the the iterator's notion of current node.
  364.    *
  365.    * Note that the iterator floats, so you don't need to do:
  366.    * <code>++iter; aDeque.PopFront();</code>
  367.    * Unless you actually want your iterator to jump 2 positions
  368.    * relative to its origin.
  369.    *
  370.    * Picture: [1 2i 3 4]
  371.    * PopFront()
  372.    * Picture: [2 3i 4]
  373.    * Note that I still happily points to object at the second index.
  374.    *
  375.    * @return  object at i'th index
  376.    */
  377.   void* GetCurrent();
  378.  
  379.   /**
  380.    * Call this method when you want to iterate all the
  381.    * members of the container, passing a functor along
  382.    * to call your code.
  383.    *
  384.    * @param   aFunctor object to call for each member
  385.    * @return  *this
  386.    */
  387.   void ForEach(nsDequeFunctor& aFunctor) const;
  388.  
  389.   /**
  390.    * Call this method when you want to iterate all the
  391.    * members of the container, calling the functor you 
  392.    * passed with each member. This process will interrupt
  393.    * if your function returns non 0 to this method.
  394.    *
  395.    * @param   aFunctor object to call for each member
  396.    * @return  first nonzero result of aFunctor or 0.
  397.    */
  398.   const void* FirstThat(nsDequeFunctor& aFunctor) const;
  399.  
  400.   protected:
  401.  
  402.   PRInt32         mIndex;
  403.   const nsDeque&  mDeque;
  404. };
  405. #endif
  406.